{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Recover a Tree From Preorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: recoverFromPreorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从先序遍历还原二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们从二叉树的根节点 <code>root</code>&nbsp;开始进行深度优先搜索。</p>\n",
    "\n",
    "<p>在遍历中的每个节点处，我们输出&nbsp;<code>D</code>&nbsp;条短划线（其中&nbsp;<code>D</code>&nbsp;是该节点的深度），然后输出该节点的值。（<em>如果节点的深度为 <code>D</code>，则其直接子节点的深度为 <code>D + 1</code>。根节点的深度为 <code>0</code>）。</em></p>\n",
    "\n",
    "<p>如果节点只有一个子节点，那么保证该子节点为左子节点。</p>\n",
    "\n",
    "<p>给出遍历输出&nbsp;<code>S</code>，还原树并返回其根节点&nbsp;<code>root</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/recover-a-tree-from-preorder-traversal.png\" style=\"height: 200px; width: 320px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;1-2--3--4-5--6--7&quot;\n",
    "<strong>输出：</strong>[1,2,5,3,4,6,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/screen-shot-2019-04-10-at-114101-pm.png\" style=\"height: 250px; width: 256px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;1-2--3---4-5--6---7&quot;\n",
    "<strong>输出：</strong>[1,2,5,3,null,6,null,4,null,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/screen-shot-2019-04-10-at-114955-pm.png\" style=\"height: 250px; width: 276px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>&quot;1-401--349---90--88&quot;\n",
    "<strong>输出：</strong>[1,401,null,349,88,90]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>原始树中的节点数介于 <code>1</code> 和 <code>1000</code> 之间。</li>\n",
    "\t<li>每个节点的值介于 <code>1</code> 和 <code>10 ^ 9</code> 之间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [recover-a-tree-from-preorder-traversal](https://leetcode.cn/problems/recover-a-tree-from-preorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [recover-a-tree-from-preorder-traversal](https://leetcode.cn/problems/recover-a-tree-from-preorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1-2--3--4-5--6--7\"', '\"1-2--3---4-5--6---7\"', '\"1-401--349---90--88\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        \n",
    "        ans = {-1:TreeNode(0)}\n",
    "\n",
    "        def addTree(val,depth):\n",
    "            ans[depth] = TreeNode(val)\n",
    "            if not ans[depth - 1].left:\n",
    "                ans[depth - 1].left = ans[depth]\n",
    "            else:\n",
    "                ans[depth - 1].right = ans[depth]\n",
    "        val,depth = '',0\n",
    "        for x in traversal:\n",
    "            if x == '-':\n",
    "                if val:\n",
    "                    addTree(int(val),depth)\n",
    "                    depth = 0\n",
    "                    val = ''\n",
    "                depth += 1\n",
    "            else:\n",
    "                val += x\n",
    "        addTree(int(val),depth)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, S: str) -> TreeNode:\n",
    "        ans = {-1: TreeNode(0)}     #字典初始化\n",
    "        def addTree(v, p):          #添加树函数\n",
    "            ans[p] = TreeNode(int(v))\n",
    "            if not ans[p - 1].left: #左子树不存在就加在左边\n",
    "                ans[p - 1].left = ans[p]\n",
    "            else:                   #反之加在右边\n",
    "                ans[p - 1].right = ans[p]\n",
    "        val, dep = '', 0            #值和对应深度初始化\n",
    "        for c in S:\n",
    "            if c != '-':\n",
    "                val += c            #累加字符来获得数字\n",
    "            elif val:               #如果是‘-’且存在val\n",
    "                addTree(val, dep)   #就把累加好的数字和对应深度添加进树\n",
    "                val, dep = '', 1    #值和对应深度重新初始化\n",
    "            else:\n",
    "                dep += 1            #连续的‘-’只加深度不加值\n",
    "        addTree(val, dep)           #末尾剩余的数字也要加进树\n",
    "        return ans[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, S: str) -> TreeNode:\n",
    "        ans = {-1: TreeNode(0)}     #字典初始化\n",
    "        def addTree(v, p):          #添加树函数\n",
    "            ans[p] = TreeNode(int(v))\n",
    "            if not ans[p - 1].left: #左子树不存在就加在左边\n",
    "                ans[p - 1].left = ans[p]\n",
    "            else:                   #反之加在右边\n",
    "                ans[p - 1].right = ans[p]\n",
    "        val, dep = '', 0            #值和对应深度初始化\n",
    "        for c in S:\n",
    "            if c != '-':\n",
    "                val += c            #累加字符来获得数字\n",
    "            elif val:               #如果是‘-’且存在val\n",
    "                addTree(val, dep)   #就把累加好的数字和对应深度添加进树\n",
    "                val, dep = '', 1    #值和对应深度重新初始化\n",
    "            else:\n",
    "                dep += 1            #连续的‘-’只加深度不加值\n",
    "        addTree(val, dep)           #末尾剩余的数字也要加进树\n",
    "        return ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        path, pos = list(), 0\n",
    "        while pos < len(traversal):\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            value = 0\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():\n",
    "                value = value * 10 + (ord(traversal[pos]) - ord('0'))\n",
    "                pos += 1\n",
    "            node = TreeNode(value)\n",
    "            if level == len(path):\n",
    "                if path:\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "                path[-1].right = node\n",
    "            path.append(node)\n",
    "        return path[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        path, pos = [], 0\n",
    "        while pos < len(traversal):\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            value = 0\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():\n",
    "                value = value * 10 + (ord(traversal[pos]) -ord('0'))\n",
    "                pos += 1\n",
    "            node = TreeNode(value)\n",
    "            if level == len(path):\n",
    "                if path:\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "                path[-1].right = node\n",
    "            path.append(node)\n",
    "        return path[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack , idx = [], 0\n",
    "        n = len(traversal)\n",
    "\n",
    "        while idx < n:\n",
    "            level , val = 0, ''\n",
    "            while idx < n and traversal[idx] == '-':\n",
    "                level += 1\n",
    "                idx += 1\n",
    "            \n",
    "            while idx < n and traversal[idx] != '-':\n",
    "                val += traversal[idx]\n",
    "                idx += 1\n",
    "            \n",
    "            while len(stack) > level:\n",
    "                stack.pop()\n",
    "            \n",
    "            node = TreeNode(int(val))\n",
    "            if stack and stack[-1].left is None:\n",
    "                stack[-1].left = node\n",
    "            elif stack and stack[-1].right is None:\n",
    "                stack[-1].right = node\n",
    "            stack.append(node)\n",
    "        \n",
    "        return stack[0]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, s: str) -> TreeNode:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        stack = []\n",
    "        while i < n:\n",
    "            num = \"\" # 2 lines\n",
    "            level = 0\n",
    "            while i < n and s[i] == \"-\":\n",
    "                level += 1\n",
    "                i += 1\n",
    "            while i < n and s[i] != \"-\":\n",
    "                num += s[i]\n",
    "                i += 1\n",
    "            while stack and len(stack) > level: # while not if\n",
    "                stack.pop()\n",
    "            node = TreeNode(int(num))\n",
    "            \n",
    "            if stack and not stack[-1].left:\n",
    "                stack[-1].left = node\n",
    "            elif stack:\n",
    "                stack[-1].right = node\n",
    "            # else: # else wrong. node 是接在left or right or root\n",
    "            stack.append(node) # important for len(stack) logic work\n",
    "        return stack[0]\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        path, pos = list(), 0\n",
    "        while pos < len(traversal):\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            value = 0\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():\n",
    "                value = value * 10 + (ord(traversal[pos]) - ord('0'))\n",
    "                pos += 1\n",
    "            node = TreeNode(value)\n",
    "\n",
    "            if level == len(path):\n",
    "                if path:\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "\n",
    "                path[-1].right = node\n",
    "            path.append(node)\n",
    "\n",
    "        return path[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\r\n",
    "        # get string and depth\r\n",
    "        path, pos = list(), 0\r\n",
    "        while pos < len(traversal):\r\n",
    "            level = 0\r\n",
    "            while traversal[pos] == '-':\r\n",
    "                level += 1\r\n",
    "                pos += 1\r\n",
    "            value = 0\r\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():\r\n",
    "                value = value * 10 + (ord(traversal[pos]) - ord('0'))\r\n",
    "                pos += 1\r\n",
    "            node = TreeNode(value)\r\n",
    "            if level == len(path):\r\n",
    "                if path:\r\n",
    "                    path[-1].left = node\r\n",
    "            else:\r\n",
    "                path = path[:level]\r\n",
    "                path[-1].right = node\r\n",
    "            path.append(node)\r\n",
    "        return path[0]\r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "\n",
    "        path = []\n",
    "        pos = 0\n",
    "        n = len(traversal)\n",
    "        while pos < n:\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            \n",
    "            val = ''\n",
    "            while pos < n and traversal[pos].isdigit():\n",
    "                val += traversal[pos]\n",
    "                pos += 1\n",
    "            val = int(val)\n",
    "            node = TreeNode(val)\n",
    "            # 构建树\n",
    "            if level == len(path):\n",
    "                if path:  # 确保root已经放进去\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "                path[-1].right = node\n",
    "            path.append(node)\n",
    "        \n",
    "        return path[0]  # root node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        road = []\n",
    "        level = 0\n",
    "        n = 0\n",
    "\n",
    "        for i in range(len(traversal)):\n",
    "            if traversal[i] == \"-\":\n",
    "                if n:\n",
    "                    road.append([level, n])\n",
    "                    level = 0\n",
    "                    n = 0\n",
    "                level += 1\n",
    "            else:\n",
    "                n = n * 10 + int(traversal[i])\n",
    "        road.append([level, n])\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(road)):\n",
    "            node = TreeNode(road[i][1])\n",
    "            if not stack:\n",
    "                stack.append([road[i][0], node])\n",
    "                continue\n",
    "            if road[i][0] > stack[-1][0]:\n",
    "                stack[-1][1].left = node\n",
    "                stack.append([road[i][0], node])\n",
    "                continue\n",
    "            while road[i][0] <= stack[-1][0]:\n",
    "                stack.pop(-1)\n",
    "            stack[-1][1].right = node\n",
    "            stack.append([road[i][0], node])\n",
    "        \n",
    "        return stack[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack, idx = [], 0\n",
    "        n = len(traversal)\n",
    "        while idx < n:\n",
    "            level, val = 0, ''\n",
    "            # '-' 出现的次数代表当前节点的深度 level\n",
    "            while idx < n and traversal[idx] == '-':\n",
    "                level += 1\n",
    "                idx += 1\n",
    "\n",
    "            # 数字出现代表当前节点的值\n",
    "            while idx < n and traversal[idx] != '-':\n",
    "                val += traversal[idx]\n",
    "                idx += 1\n",
    "            \n",
    "            # 确保当前节点所处的 level 与 节点深度对应\n",
    "            while len(stack) > level:\n",
    "                stack.pop()\n",
    "            \n",
    "            # 构建子节点，按照左右的顺序\n",
    "            node = TreeNode(int(val))\n",
    "            if stack and stack[-1].left is None:\n",
    "                stack[-1].left = node\n",
    "            elif stack and stack[-1].right is None:\n",
    "                stack[-1].right = node\n",
    "            # 不同 level 的放在不同的stack的索引\n",
    "            stack.append(node)\n",
    "\n",
    "        # print(len(stack), stack)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, s: str) -> Optional[TreeNode]:\n",
    "        stack = [] \n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i <n:\n",
    "            #for i in range(n):\n",
    "            curLevel = 0 #构建 当前节点所属的level\n",
    "            while i < n and s[i] == '-': #记录连字符的数量\n",
    "                curLevel +=1 #统计他的level\n",
    "                i+=1 #扫描的指针加一\n",
    "            start = i #记录下节点值 字符串开始位置\n",
    "\n",
    "            while i <n and s[i] != '-':\n",
    "                i+=1\n",
    "\n",
    "            val = int(s[start:i]) #取出节点值 #要转换为整形数字)\n",
    "            curNode = TreeNode(val) #创建节点\n",
    "            if  not stack: #此时栈为空\n",
    "                stack.append(curNode)\n",
    "                continue#直接跳出 根节点没有父节点\n",
    "            while  len(stack) > curLevel:\n",
    "                stack.pop()#只要 栈高 大于>当前节点的 Level，栈顶就出栈，栈顶的子节点已经找完，\n",
    "                            #即当前元素已经从左子树跳到了右子树了\n",
    "            if stack[-1].left: #栈顶为父节点，但是 左儿子已经存在\n",
    "                stack[len(stack)-1].right = curNode #当前节点成为右儿子\n",
    "            else:\n",
    "                stack[-1].left =curNode #否则成为左儿子\n",
    "            \n",
    "            stack.append(curNode) #当前节点也是父节点， 入栈等 儿子 \n",
    "            #i+=1\n",
    "        return stack[0] #栈底为根节点\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        queue = list()\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        while right < len(traversal) and traversal[right] != '-':\n",
    "            right += 1\n",
    "\n",
    "        queue.append(TreeNode(int(traversal[left:right])))\n",
    "\n",
    "        left = right\n",
    "        right = left\n",
    "\n",
    "        while right < len(traversal):\n",
    "            while right < len(traversal) and traversal[right] == '-':\n",
    "                right += 1\n",
    "\n",
    "            start = right\n",
    "            end = right\n",
    "\n",
    "            while end < len(traversal) and traversal[end] != '-':\n",
    "                end += 1\n",
    "\n",
    "            depth = right - left\n",
    "            node = TreeNode(int(traversal[start:end]))\n",
    "\n",
    "            if len(queue) == depth:\n",
    "                queue[-1].left = node\n",
    "                queue.append(node)\n",
    "\n",
    "            else:\n",
    "                while len(queue) > depth:\n",
    "                    queue.pop()\n",
    "\n",
    "                queue[-1].right = node\n",
    "                queue.append(node)\n",
    "\n",
    "            left = end\n",
    "            right = left\n",
    "\n",
    "        return queue[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        dict_tree = {-1:TreeNode(0)}\n",
    "\n",
    "        def addTree(val,dep):\n",
    "            dict_tree[dep] = TreeNode(int(val))\n",
    "            if not dict_tree[dep-1].left:\n",
    "                dict_tree[dep-1].left = dict_tree[dep]\n",
    "            else:\n",
    "                dict_tree[dep-1].right = dict_tree[dep]\n",
    "\n",
    "        val,dep = \"\",0\n",
    "        for c in traversal:\n",
    "            if c != \"-\":\n",
    "                val += c\n",
    "            elif val:\n",
    "                addTree(val,dep)\n",
    "                val,dep = \"\",1\n",
    "            else:\n",
    "                dep += 1\n",
    "        addTree(val,dep)\n",
    "\n",
    "        return dict_tree[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack, idx = [], 0\n",
    "        n = len(traversal)\n",
    "        while idx < n:\n",
    "            depth, val = 0, ''\n",
    "            while idx < n and traversal[idx] == '-':\n",
    "                idx += 1\n",
    "                depth += 1\n",
    "            while idx < n and traversal[idx] != '-':\n",
    "                val += traversal[idx]\n",
    "                idx += 1\n",
    "            \n",
    "            while len(stack) > depth:\n",
    "                stack.pop()\n",
    "\n",
    "            node = TreeNode(int(val))\n",
    "            if stack and stack[-1].left is None:\n",
    "                stack[-1].left = node\n",
    "            elif stack and stack[-1].right is None:\n",
    "                stack[-1].right = node\n",
    "\n",
    "            stack.append(node)\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < len(traversal):\n",
    "            level = 0\n",
    "            while traversal[i] == '-':\n",
    "                level += 1\n",
    "                i += 1\n",
    "            value = 0\n",
    "            while i < len(traversal) and traversal[i].isdigit():\n",
    "                value = value * 10 + int(traversal[i])\n",
    "                i += 1\n",
    "            node = TreeNode(value)\n",
    "            if level == len(stack):\n",
    "                if stack:\n",
    "                    stack[-1].left = node\n",
    "            else:\n",
    "                stack = stack[:level]\n",
    "                stack[-1].right = node\n",
    "            stack.append(node)\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        n = len(traversal)\n",
    "        i = 0 \n",
    "        def dfs(d):\n",
    "            nonlocal i \n",
    "            if i == n:\n",
    "                return None  \n",
    "            val = l = 0 \n",
    "            while i < n and traversal[i] == '-':\n",
    "                i+=1\n",
    "                l+=1\n",
    "            if l < d:\n",
    "                i -= l\n",
    "                return None \n",
    "            while i < n and traversal[i].isdigit():\n",
    "                val = val * 10 + int(traversal[i]) \n",
    "                i+=1\n",
    "            if val == 0:\n",
    "                return None \n",
    "            root = TreeNode(val)\n",
    "            root.left = dfs(d+1)\n",
    "            root.right = dfs(d+1)\n",
    "            return root \n",
    "          \n",
    "        root = dfs(0) \n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack, pos = [], 0\n",
    "        while pos < len(traversal):\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            val = 0\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():\n",
    "                val = val * 10 + (ord(traversal[pos]) - ord('0'))\n",
    "                pos += 1\n",
    "            node = TreeNode(val)\n",
    "            if level == len(stack):\n",
    "                if stack:\n",
    "                    stack[-1].left = node\n",
    "            else:\n",
    "                stack = stack[:level]\n",
    "                stack[-1].right = node\n",
    "            stack.append(node)\n",
    "        return stack[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack, idx = [], 0\n",
    "        n = len(traversal)\n",
    "        while idx < n:\n",
    "            level, val = 0, ''\n",
    "            # '-' 出现的次数代表当前节点的深度 level\n",
    "            while idx < n and traversal[idx] == '-':\n",
    "                level += 1\n",
    "                idx += 1\n",
    "\n",
    "            # 数字出现代表当前节点的值\n",
    "            while idx < n and traversal[idx] != '-':\n",
    "                val += traversal[idx]\n",
    "                idx += 1\n",
    "            \n",
    "            # 确保当前节点所处的 level 与 节点深度对应\n",
    "            while len(stack) > level:\n",
    "                stack.pop()\n",
    "            \n",
    "            # 构建子节点，按照左右的顺序\n",
    "            node = TreeNode(int(val))\n",
    "            if stack and stack[-1].left is None:\n",
    "                stack[-1].left = node\n",
    "            elif stack and stack[-1].right is None:\n",
    "                stack[-1].right = node\n",
    "            # 不同 level 的放在不同的stack的索引\n",
    "            stack.append(node)\n",
    "\n",
    "        # print(len(stack), stack)\n",
    "        return stack[0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        q = []\n",
    "        depth = 0 \n",
    "        i = 0\n",
    "        while i < len(traversal):\n",
    "            depth = 0\n",
    "            while traversal[i] == '-':\n",
    "                depth += 1\n",
    "                i += 1\n",
    "            value = 0\n",
    "            while i < len(traversal) and traversal[i].isdigit():\n",
    "                value = value * 10 + (ord(traversal[i]) - ord('0'))\n",
    "                i += 1\n",
    "            node = TreeNode(value)\n",
    "            if depth == len(q):\n",
    "                if q:\n",
    "                    q[-1].left = node\n",
    "            else:\n",
    "                q = q[:depth]\n",
    "                q[-1].right = node\n",
    "            q.append(node)\n",
    "        return q[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        #root=TreeNode(traversal[0])\n",
    "        i,j=0,1\n",
    "        n=len(traversal)\n",
    "        ls=[]\n",
    "        i,j=0,0\n",
    "        c=0\n",
    "        isnum=True\n",
    "        while i<n:\n",
    "            if isnum:\n",
    "                while j<n and traversal[j]!=\"-\":\n",
    "                    j+=1\n",
    "                ch=int(traversal[i:j])\n",
    "                ls.append((c,ch))\n",
    "                c=0\n",
    "                i=j\n",
    "                isnum=False\n",
    "            else:\n",
    "                while j<n and traversal[j]==\"-\":\n",
    "                    c+=1\n",
    "                    j+=1\n",
    "                i=j\n",
    "                isnum=True\n",
    "        #print(ls[0][1])\n",
    "\n",
    "        root=TreeNode(ls[0][1])\n",
    "        ls.pop(0)\n",
    "        q=[(0,root)]\n",
    "        #last=0\n",
    "        for level,ch in ls:\n",
    "            #print(level,ch,q)\n",
    "            while q and level<=q[-1][0]:\n",
    "                q.pop()\n",
    "            #print(level,q[-1])\n",
    "            if level>q[-1][0]:\n",
    "                now=TreeNode(ch)\n",
    "                if q[-1][1].left:\n",
    "                    q[-1][1].right=now\n",
    "                else:\n",
    "                    q[-1][1].left=now\n",
    "                q.append((level,now))\n",
    "        #print(q)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        s = traversal\n",
    "        i, n = 0, len(s)\n",
    "        st = []\n",
    "        while i < n:\n",
    "            cur_level = 0\n",
    "            while i < n and s[i] == '-':\n",
    "                cur_level += 1\n",
    "                i += 1\n",
    "            start = i\n",
    "            while i < n and s[i] != '-':\n",
    "                i += 1\n",
    "            node = TreeNode(int(s[start:i]))\n",
    "            if not st:\n",
    "                st.append(node) \n",
    "                continue\n",
    "            while len(st) >  cur_level:\n",
    "                st.pop()\n",
    "            if st[-1].left:\n",
    "                st[-1].right = node\n",
    "            else:\n",
    "                st[-1].left = node\n",
    "            st.append(node)\n",
    "        return st[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        n = len(traversal)\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            lev = 0\n",
    "            while i < n and traversal[i] == '-':\n",
    "                lev += 1 \n",
    "                i += 1 \n",
    "            val = 0\n",
    "            while i < n and traversal[i].isdigit():\n",
    "                val = val * 10 + int(traversal[i])\n",
    "                i += 1\n",
    "            new = TreeNode(val)\n",
    "            if len(stack) == lev:\n",
    "                if stack:\n",
    "                    stack[-1].left = new \n",
    "            else:\n",
    "                stack = stack[: lev]\n",
    "                stack[-1].right = new \n",
    "            stack.append(new)\n",
    "        return stack[0]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        j = 0\n",
    "        number = 0\n",
    "        n = len(traversal)\n",
    "        while j < n and traversal[j] != '-':\n",
    "            number = number * 10 + int(traversal[j])\n",
    "            j += 1\n",
    "            pass\n",
    "\n",
    "        s = [TreeNode(number)]\n",
    "        count = 0\n",
    "        number = 0\n",
    "        for i in range(j, n):\n",
    "            if traversal[i] == '-':\n",
    "                count += 1\n",
    "                pass\n",
    "            else:\n",
    "                number = number * 10 + int(traversal[i])\n",
    "                if i == n - 1 or traversal[i + 1] == '-':\n",
    "                    node = TreeNode(number)\n",
    "                    if count >= len(s):\n",
    "                        s[len(s) - 1].left = node\n",
    "                        s.append(node)\n",
    "                        pass\n",
    "                    else:\n",
    "                        while count < len(s):\n",
    "                            s.pop()\n",
    "                            pass\n",
    "                        s[len(s) - 1].right = node\n",
    "                        s.append(node)\n",
    "                    count = 0\n",
    "                    number = 0\n",
    "                    pass\n",
    "        return s[0]\n",
    "        pass\n",
    "\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        #多给了一个深度的信息，先处理这个信息 \n",
    "        #每次的深度就是两次数字位坐标的差值 - 1\n",
    "        last = 0\n",
    "        ls = [] \n",
    "        i = 0\n",
    "        while i < len(traversal):\n",
    "            if traversal[i].isdigit():\n",
    "                num = ''\n",
    "                cnt = i - last\n",
    "                while i < len(traversal) and traversal[i].isdigit():\n",
    "                    num += traversal[i]\n",
    "                    i += 1 \n",
    "                ls.append((int(num), cnt))\n",
    "                last = i\n",
    "                continue\n",
    "            i += 1\n",
    "        #还是使用递归吧，当深度降回到1的时候就是换到右子树\n",
    "        return self.recoverFromPreorderHelper(ls)\n",
    "\n",
    "    def recoverFromPreorderHelper(self, ls):\n",
    "        if len(ls) == 0:\n",
    "            return None\n",
    "        if len(ls) == 1:\n",
    "            return TreeNode(ls[0][0])\n",
    "\n",
    "        root = ls[0]\n",
    "        idx = 1\n",
    "        left, right = [], []\n",
    "        while idx < len(ls):\n",
    "            left.append(ls[idx])\n",
    "            idx += 1\n",
    "            if idx >= len(ls) or ls[idx][1] == root[1] + 1:\n",
    "                break\n",
    "        if idx < len(ls):\n",
    "            right += ls[idx:]\n",
    "        Root = TreeNode(root[0])\n",
    "        Root.left = self.recoverFromPreorderHelper(left)\n",
    "        Root.right = self.recoverFromPreorderHelper(right)\n",
    "        return Root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> TreeNode:\n",
    "        path, pos = list(), 0\n",
    "        while pos < len(traversal):\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            value = 0\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():\n",
    "                value = value * 10 + (ord(traversal[pos]) - ord('0'))\n",
    "                pos += 1\n",
    "            node = TreeNode(value)\n",
    "            if level == len(path):\n",
    "                if path:\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "                path[-1].right = node\n",
    "            path.append(node)\n",
    "        return path[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(s, size):\n",
    "            if not s:\n",
    "                return None\n",
    "            \n",
    "            i = size\n",
    "\n",
    "            start = i\n",
    "            while i < len(s) and s[i] != '-':\n",
    "                i += 1\n",
    "            \n",
    "            node = TreeNode(int(s[start:i]))\n",
    "            if i == len(s):\n",
    "                return node\n",
    "\n",
    "            left_start = i\n",
    "\n",
    "\n",
    "            while i < len(s) and s[i] == '-':\n",
    "                i += 1\n",
    "            while i < len(s) and s[i].isdigit():\n",
    "                i += 1\n",
    "            \n",
    "            flag = False\n",
    "            while i < len(s):\n",
    "                start = i\n",
    "                while i < len(s) and s[i] == '-':\n",
    "                    i += 1\n",
    "                \n",
    "                length = i - 1 - start + 1\n",
    "                if length == size + 1:\n",
    "                    flag = True\n",
    "                    break\n",
    "                \n",
    "                while i < len(s) and s[i].isdigit():\n",
    "                    i += 1\n",
    "\n",
    "\n",
    "            \n",
    "            if not flag:\n",
    "                node.left = dfs(s[left_start:], size + 1) \n",
    "                return node\n",
    "            \n",
    "\n",
    "            node.left = dfs(s[left_start:start], size + 1)\n",
    "            node.right = dfs(s[start:], size + 1)\n",
    "\n",
    "            return node\n",
    "\n",
    "\n",
    "        return dfs(traversal, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "    \n",
    "        dic=collections.defaultdict(list)\n",
    "        level=0\n",
    "        num=0\n",
    "        n=len(traversal)\n",
    "        for i,v in enumerate(traversal):\n",
    "            if v==\"-\":\n",
    "                level+=1\n",
    "            else:\n",
    "            \n",
    "                num=num*10+int(v)\n",
    "                if i==n-1 or traversal[i+1]==\"-\":\n",
    "                    node=TreeNode(num)\n",
    "                    dic[level].append(node)\n",
    "                    if dic[level-1]:\n",
    "                        if dic[level-1][-1].left:\n",
    "                            dic[level-1][-1].right=node\n",
    "                        else:\n",
    "                            dic[level-1][-1].left=node\n",
    "                    num=0\n",
    "                    level=0\n",
    "        return dic[0][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        queue = list()\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        while right < len(traversal):\n",
    "            while right < len(traversal) and traversal[right] == '-':\n",
    "                right += 1\n",
    "\n",
    "            start = right\n",
    "            end = right\n",
    "\n",
    "            while end < len(traversal) and traversal[end] != '-':\n",
    "                end += 1\n",
    "\n",
    "            depth = right - left\n",
    "            node = TreeNode(int(traversal[start:end]))\n",
    "\n",
    "            if len(queue) == depth:\n",
    "                if len(queue) > 0:\n",
    "                    queue[-1].left = node\n",
    "                queue.append(node)\n",
    "\n",
    "            else:\n",
    "                while len(queue) > depth:\n",
    "                    queue.pop()\n",
    "\n",
    "                queue[-1].right = node\n",
    "                queue.append(node)\n",
    "\n",
    "            left = end\n",
    "            right = left\n",
    "\n",
    "        return queue[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, S: str) -> TreeNode:\n",
    "        ans = {-1: TreeNode(0)}    \n",
    "        def addTree(v, p):        \n",
    "            ans[p] = TreeNode(int(v))\n",
    "            if not ans[p - 1].left:\n",
    "                ans[p - 1].left = ans[p]\n",
    "            else:                  \n",
    "                ans[p - 1].right = ans[p]\n",
    "        val, dep = '', 0          \n",
    "        for c in S:\n",
    "            if c != '-':\n",
    "                val += c          \n",
    "            elif val:              \n",
    "                addTree(val, dep)   \n",
    "                val, dep = '', 1    \n",
    "            else:\n",
    "                dep += 1            \n",
    "        addTree(val, dep)        \n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, s: str) -> TreeNode:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        stack = []\n",
    "        while i < n:\n",
    "            num = \"\" # 2 lines\n",
    "            level = 0\n",
    "            while i < n and s[i] == \"-\":\n",
    "                level += 1\n",
    "                i += 1\n",
    "            while i < n and s[i] != \"-\":\n",
    "                num += s[i]\n",
    "                i += 1\n",
    "            while stack and len(stack) > level: # while not if\n",
    "                stack.pop()\n",
    "            node = TreeNode(int(num))\n",
    "            \n",
    "            if stack and not stack[-1].left:\n",
    "                stack[-1].left = node\n",
    "            elif stack:\n",
    "                stack[-1].right = node\n",
    "            # else: # else wrong\n",
    "            stack.append(node) # important for len(stack) logic work\n",
    "        return stack[0]\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, s: str) -> Optional[TreeNode]:\n",
    "       \n",
    "        index = 0 #遍历字符用的指针 \n",
    "        def buildTree(s,level): #构建当前 level 层的树\n",
    "            nonlocal index  #在函数内部 要调用非局部变量 无论global还是nonlocal 必须优先 声明，哪怕只是在条件判断里面不更改其值也要优先声明 非局部变量。 即 在函数内部 第一次调用之前就要 声明，在内部函数的一开始就声明 非局部 不然会报错\n",
    "            curLevel =0 #点前遇到节点的level 初始化\n",
    "            n = len(s)\n",
    "            while index < n and s[index] == '-':\n",
    "                curLevel +=1 #计算 当前节点的level\n",
    "                \n",
    "                index +=1\n",
    "            if curLevel < level:\n",
    "                index -= curLevel\n",
    "                return None\n",
    "            start = index\n",
    "            while index < n and s[index] != '-':\n",
    "                index +=1\n",
    "\n",
    "            val = int(s[start:index])\n",
    "            curNode = TreeNode(val)\n",
    "\n",
    "            curNode.left = buildTree(s, level+1)\n",
    "            curNode.right = buildTree(s, level+1)\n",
    "            return curNode\n",
    "        return buildTree(s, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "\n",
    "        path = []\n",
    "        pos = 0\n",
    "        n = len(traversal)\n",
    "        while pos < n:\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            \n",
    "            val = ''\n",
    "            while pos < n and traversal[pos].isdigit():\n",
    "                val += traversal[pos]\n",
    "                pos += 1\n",
    "            val = int(val)\n",
    "            node = TreeNode(val)\n",
    "            # 构建树\n",
    "            if level == len(path):\n",
    "                if path:  # 确保root已经放进去\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "                path[-1].right = node\n",
    "            path.append(node)\n",
    "        \n",
    "        return path[0]  # root node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        #多给了一个深度的信息，先处理这个信息 \n",
    "        #每次的深度就是两次数字位坐标的差值 - 1\n",
    "        last = 0\n",
    "        ls = [] \n",
    "        i = 0\n",
    "        while i < len(traversal):\n",
    "            if traversal[i].isdigit():\n",
    "                num = ''\n",
    "                cnt = i - last\n",
    "                while i < len(traversal) and traversal[i].isdigit():\n",
    "                    num += traversal[i]\n",
    "                    i += 1 \n",
    "                ls.append((int(num), cnt))\n",
    "                last = i\n",
    "                continue\n",
    "            i += 1\n",
    "        #还是使用递归吧，当深度降回到1的时候就是换到右子树\n",
    "        return self.recoverFromPreorderHelper(ls)\n",
    "\n",
    "    def recoverFromPreorderHelper(self, ls):\n",
    "        if len(ls) == 0:\n",
    "            return None\n",
    "        if len(ls) == 1:\n",
    "            return TreeNode(ls[0][0])\n",
    "\n",
    "        root = ls[0]\n",
    "        idx = 1\n",
    "        left, right = [], []\n",
    "        while idx < len(ls):\n",
    "            left.append(ls[idx])\n",
    "            idx += 1\n",
    "            if idx >= len(ls) or ls[idx][1] == root[1] + 1:\n",
    "                break\n",
    "        if idx < len(ls):\n",
    "            right += ls[idx:]\n",
    "        Root = TreeNode(root[0])\n",
    "        Root.left = self.recoverFromPreorderHelper(left)\n",
    "        Root.right = self.recoverFromPreorderHelper(right)\n",
    "        return Root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        path = []\n",
    "        pos = 0\n",
    "        n = len(traversal)\n",
    "\n",
    "\n",
    "        while pos < n:\n",
    "            level = 0\n",
    "            while traversal[pos] == '-':\n",
    "                pos += 1\n",
    "                level += 1\n",
    "            \n",
    "            value = 0\n",
    "            while pos<n and traversal[pos].isdigit():\n",
    "                value = value*10 + ord(traversal[pos])-ord('0')\n",
    "                pos+=1\n",
    "            \n",
    "            node = TreeNode(value)\n",
    "            if level==len(path):\n",
    "                if len(path):\n",
    "                    path[-1].left = node\n",
    "            else:\n",
    "                path = path[:level]\n",
    "                path[-1].right = node\n",
    "            \n",
    "            path.append(node)\n",
    "        \n",
    "        return path[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        x = re.split(r'((?<=\\d)(?=-))', traversal)\n",
    "        print(x)   \n",
    "        root = TreeNode(int(x[0]))  \n",
    "        stack = [root]\n",
    "        lastLevel = 0\n",
    "        for i in range(1, len(x)):\n",
    "            if not x[i]: continue\n",
    "            level = x[i].count('-')\n",
    "            val = x[i][level:]\n",
    "            newNode = TreeNode(int(val))\n",
    "            if level > lastLevel:\n",
    "                stack[-1].left = newNode\n",
    "            else:\n",
    "                for i in range(lastLevel - level + 1):\n",
    "                    lastNode = stack.pop()\n",
    "                stack[-1].right = newNode\n",
    "            stack.append(newNode)\n",
    "            lastLevel = level\n",
    "        return root\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        stack, idx = [], 0\n",
    "        n = len(traversal)\n",
    "        while idx < n:\n",
    "            level, val = 0, ''\n",
    "            while idx < n and traversal[idx] == '-':\n",
    "                level+=1\n",
    "                idx+=1\n",
    "            while idx < n and traversal[idx] != '-':\n",
    "                val += traversal[idx]\n",
    "                idx += 1\n",
    "            while len(stack) > level:\n",
    "                stack.pop()\n",
    "            node = TreeNode(int(val))\n",
    "            if stack and stack[-1].left is None:\n",
    "                stack[-1].left = node\n",
    "            elif stack and stack[-1].right is None:\n",
    "                stack[-1].right = node\n",
    "            stack.append(node)\n",
    "\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        queue = list()\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        while right < len(traversal) and traversal[right] != '-':\n",
    "            right += 1\n",
    "\n",
    "        queue.append(TreeNode(int(traversal[left:right])))\n",
    "\n",
    "        left = right\n",
    "        right = left\n",
    "\n",
    "        while right < len(traversal):\n",
    "            while right < len(traversal) and traversal[right] == '-':\n",
    "                right += 1\n",
    "\n",
    "            start = right\n",
    "            end = right\n",
    "\n",
    "            while end < len(traversal) and traversal[end] != '-':\n",
    "                end += 1\n",
    "\n",
    "            depth = right - left\n",
    "            node = TreeNode(int(traversal[start:end]))\n",
    "\n",
    "            if len(queue) == depth:\n",
    "                queue[-1].left = node\n",
    "\n",
    "            else:\n",
    "                while len(queue) > depth:\n",
    "                    queue.pop()\n",
    "\n",
    "                queue[-1].right = node\n",
    "                \n",
    "            queue.append(node)\n",
    "\n",
    "            left = end\n",
    "            right = left\n",
    "\n",
    "        return queue[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        def getNum(s,i):\n",
    "            res=0\n",
    "            i=i-1\n",
    "            while(i>=0 and s[i]=='-'):\n",
    "                res+=1\n",
    "                i-=1\n",
    "            return res\n",
    "        def build(qian,k):\n",
    "            if qian=='': return None\n",
    "            # print(qian,k)\n",
    "            mid=0\n",
    "            middx=len(qian)\n",
    "            for i in range(len(qian)):\n",
    "                if qian[i]=='-':\n",
    "                    middx=i\n",
    "                    break\n",
    "            mid=int(qian[0:middx])\n",
    "            dx=len(qian)+k\n",
    "            for i in range(middx+k+1,len(qian)):\n",
    "                if ord('0')<= ord(qian[i])<=ord('9'):\n",
    "                    n=getNum(qian,i)\n",
    "                    if n==k:\n",
    "                        dx=i\n",
    "                        break\n",
    "\n",
    "            left = qian[middx+k:dx-k]\n",
    "            right=qian[dx:]\n",
    "            midNode=TreeNode(mid)\n",
    "            lt=build(left,k+1)\n",
    "            rt=build(right,k+1)\n",
    "            if lt is None:\n",
    "                midNode.left=rt\n",
    "                midNode.right=None\n",
    "            else:\n",
    "                midNode.left=lt\n",
    "                midNode.right=rt\n",
    "            return midNode\n",
    "        return build(traversal,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> TreeNode:\n",
    "        path, pos = list(), 0  # 使用列表path存储遍历过程中的路径节点，pos表示当前在traversal字符串中的位置\n",
    "        while pos < len(traversal):  # 当pos小于traversal字符串长度时循环\n",
    "            level = 0  # 记录当前节点的层级\n",
    "            while traversal[pos] == '-':  # 统计当前节点的层级\n",
    "                level += 1\n",
    "                pos += 1\n",
    "            value = 0  # 记录当前节点的值\n",
    "            while pos < len(traversal) and traversal[pos].isdigit():  # 解析当前节点的值，将连续的数字字符转为整数\n",
    "                value = value * 10 + (ord(traversal[pos]) - ord('0'))\n",
    "                pos += 1\n",
    "            node = TreeNode(value)  # 创建节点对象\n",
    "            if level == len(path):  # 如果level等于path列表的长度，说明当前节点是上一个节点的左子节点\n",
    "                if path:  # 如果path不为空，将当前节点作为上一个节点的左子节点\n",
    "                    path[-1].left = node\n",
    "            else:  # 如果level小于path列表的长度，说明当前节点是某个祖先节点的右子节点\n",
    "                path = path[:level]  # 保留属于当前节点所在层级的祖先节点\n",
    "                path[-1].right = node  # 将当前节点作为其父节点的右子节点\n",
    "            path.append(node)  # 将当前节点添加到path列表中\n",
    "        return path[0]  # 返回恢复后的二叉树的根节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        values = traversal.split(\"-\")\n",
    "        # ['1', '2', '', '3', '', '4', '5', '', '6', '', '7']\n",
    "        nsize = len(values)\n",
    "        root = TreeNode(int(values[0]))\n",
    "\n",
    "        nstack = [(root, 0)]\n",
    "        dep = 1\n",
    "        i = 1\n",
    "        while i<nsize:\n",
    "            if values[i]!=\"\":\n",
    "                newnode = TreeNode(int(values[i]))\n",
    "                while nstack:\n",
    "                    # print([(n.val,d) for n,d in nstack])\n",
    "                    pnode, prev_dep = nstack.pop()\n",
    "                    if dep == prev_dep:\n",
    "                        pnode, prev_dep = nstack[-1]\n",
    "                        pnode.right = newnode\n",
    "                        nstack.append( (newnode, dep) )\n",
    "                        break\n",
    "                    elif dep > prev_dep:\n",
    "                        nstack.append( (pnode, prev_dep) )\n",
    "                        pnode.left = newnode\n",
    "                        # print(pnode)\n",
    "                        nstack.append( (newnode, dep) )\n",
    "                        break\n",
    "                    else: #dep < prev_dep\n",
    "                        pass\n",
    "                dep = 1\n",
    "            else:\n",
    "                dep+=1\n",
    "            i+=1\n",
    "\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str):\n",
    "        if traversal == None:\n",
    "            return None \n",
    "\n",
    "        n = len(traversal)\n",
    "        return self.process(traversal, 0, n - 1, 0) \n",
    "    \n",
    "    def process(self, s, l, r, depth):\n",
    "        \"\"\"\n",
    "        重建二叉树\n",
    "        Args:\n",
    "            s (str): 原始字符串\n",
    "            l (int): 当前二叉树的起始索引\n",
    "            r (int): 当前二叉树的结束索引\n",
    "            depth (int): 当前根节点的深度\n",
    "        returns (TreeNode): 还原后的二叉树根节点\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        n = len(s)\n",
    "        if l > r or r >= n:\n",
    "            return None \n",
    "        \n",
    "        #查找根节点的值\n",
    "        val_end = l \n",
    "        while val_end <= r and s[val_end] in '0123456789':\n",
    "            val_end += 1\n",
    "        \n",
    "        #根节点的值即为s[l: val_end]\n",
    "        root_val = 0\n",
    "        cur = l  \n",
    "        while cur < val_end:\n",
    "            root_val = 10 * root_val + int(s[cur])\n",
    "            cur += 1\n",
    "        \n",
    "        \n",
    "        #根据(depth + 1) * '-'的位置查找root节点的左右子树的索引\n",
    "        left_start, right_start = val_end, val_end \n",
    "        while r - left_start >= depth + 1:  #遍历每个索引, 查找\n",
    "            if s[left_start: left_start + depth + 1] == '-' * (depth + 1) and (s[left_start + depth + 1] != '-' and s[left_start - 1] != '-'):\n",
    "                break \n",
    "            else:\n",
    "                left_start += 1\n",
    "\n",
    "        left_start += (depth + 1)\n",
    "\n",
    "        #同理求证右子树的起始索引\n",
    "        right_start = left_start \n",
    "        while right_start <= r:  #遍历每个索引, 查找\n",
    "            # print(\"当前的起始索引为:\", right_start)\n",
    "            # print(\"当前子串:\", s[right_start: right_start + depth + 1])\n",
    "            # print(\"当前要寻找的子串:\", '-' * (depth + 1))\n",
    "            # print('\\n')\n",
    "            if right_start + depth + 1 <= n and s[right_start: right_start + depth + 1] == '-' * (depth + 1) and (s[right_start + depth + 1] != '-' and s[right_start - 1] != '-'):\n",
    "                break\n",
    "             \n",
    "            else:\n",
    "                right_start += 1\n",
    "        \n",
    "        \n",
    "        mid = right_start - 1\n",
    "        right_start += (depth + 1)\n",
    "        \n",
    "        # print(left_start, mid, right_start)\n",
    "        root = TreeNode(root_val)\n",
    "        left = self.process(s, left_start, mid, depth + 1)\n",
    "        right = self.process(s, right_start, r, depth + 1)\n",
    "\n",
    "        root.left = left \n",
    "        root.right = right \n",
    "\n",
    "        return root \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        #多给了一个深度的信息，先处理这个信息 \n",
    "        #每次的深度就是两次数字位坐标的差值 - 1\n",
    "        last = 0\n",
    "        ls = [] \n",
    "        i = 0\n",
    "        while i < len(traversal):\n",
    "            if traversal[i].isdigit():\n",
    "                num = ''\n",
    "                cnt = i - last\n",
    "                while i < len(traversal) and traversal[i].isdigit():\n",
    "                    num += traversal[i]\n",
    "                    i += 1 \n",
    "                ls.append((int(num), cnt))\n",
    "                last = i\n",
    "                continue\n",
    "            i += 1\n",
    "        #还是使用递归吧，当深度降回到1的时候就是换到右子树\n",
    "        return self.recoverFromPreorderHelper(ls)\n",
    "\n",
    "    def recoverFromPreorderHelper(self, ls):\n",
    "        if len(ls) == 0:\n",
    "            return None\n",
    "        if len(ls) == 1:\n",
    "            return TreeNode(ls[0][0])\n",
    "\n",
    "        root = ls[0]\n",
    "        idx = 1\n",
    "        left, right = [], []\n",
    "        while idx < len(ls):\n",
    "            left.append(ls[idx])\n",
    "            idx += 1\n",
    "            if idx >= len(ls) or ls[idx][1] == root[1] + 1:\n",
    "                break\n",
    "        if idx < len(ls):\n",
    "            right += ls[idx:]\n",
    "        Root = TreeNode(root[0])\n",
    "        Root.left = self.recoverFromPreorderHelper(left)\n",
    "        Root.right = self.recoverFromPreorderHelper(right)\n",
    "        return Root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        if len(traversal) == 0:\n",
    "            return None\n",
    "        i = 0\n",
    "        while i < len(traversal) and traversal[i] != '-':\n",
    "            i += 1\n",
    "        val = int(traversal[:i])\n",
    "        root = TreeNode(val)\n",
    "        \n",
    "        j = i\n",
    "        print(traversal)\n",
    "        while j < len(traversal) and traversal[j] == '-':\n",
    "            j += 1\n",
    "        D = j - i\n",
    "        i = j\n",
    "        cnt = 0\n",
    "        while j < len(traversal):\n",
    "            if traversal[j] == '-':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                if cnt == D:\n",
    "                    break\n",
    "                cnt = 0\n",
    "            j += 1\n",
    "        if cnt == D:\n",
    "            root.left = self.recoverFromPreorder(traversal[i:j-D])\n",
    "            root.right = self.recoverFromPreorder(traversal[j:])\n",
    "        else:\n",
    "            root.left = self.recoverFromPreorder(traversal[i:])\n",
    "            root.right = None\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "\n",
    "        def backtrack(s,depth):\n",
    "            if not s:\n",
    "                return None\n",
    "            # 先将root的值取出来\n",
    "            root_val = 0\n",
    "            for i in s:\n",
    "                if i != '-': \n",
    "                    root_val = root_val*10 + int(i) \n",
    "                else:\n",
    "                    break \n",
    "            root = TreeNode(root_val)\n",
    "            # 找depth+1个\"-\"后进行分割\n",
    "            mask = (depth+1)*'-'\n",
    "            nxt = []\n",
    "            for j in range(1,len(s)-depth-1):\n",
    "                if s[j:j+depth+1] == mask and s[j+depth+1] != '-'  and s[j-1] != '-':\n",
    "                    nxt.append(j+depth+1)\n",
    "            if len(nxt) > 0:\n",
    "                if len(nxt) > 1:\n",
    "                    L = s[nxt[0]:nxt[1]-depth-1]\n",
    "                    R = s[nxt[1]:]\n",
    "                    root.left = backtrack(L,depth+1)\n",
    "                    root.right = backtrack(R,depth+1)\n",
    "                else:\n",
    "                    L = s[nxt[0]:]\n",
    "                    root.left = backtrack(L,depth+1)\n",
    "            return root\n",
    "        return backtrack(traversal,0)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        traversal = traversal.split('-')\n",
    "        traversal = [int(a) if a else 0 for a in traversal]\n",
    "\n",
    "        root = TreeNode(traversal[0])\n",
    "        nodes = [root]\n",
    "        i, n = 1, len(traversal)\n",
    "        while i < n:\n",
    "            deep = 0\n",
    "            while i < n and traversal[i] == 0:\n",
    "                deep += 1\n",
    "                i += 1\n",
    "            nownode = TreeNode(traversal[i])\n",
    "            if not nodes[deep].left:\n",
    "                nodes[deep].left = nownode\n",
    "            else:\n",
    "                nodes[deep].right = nownode\n",
    "            if deep + 1 >= len(nodes):\n",
    "                nodes.append(nownode)\n",
    "            else:\n",
    "                nodes[deep + 1] = nownode\n",
    "            i += 1\n",
    "        return root\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        sp=traversal.split('-')\n",
    "        ndList=list()\n",
    "        k=0\n",
    "        for i in sp:\n",
    "            if i=='':\n",
    "                k+=1\n",
    "            else:\n",
    "                ndList.append((k,int(i)))\n",
    "                k=1\n",
    "        def build(ndList):\n",
    "            if len(ndList)==0: return None\n",
    "            # print(ndList)\n",
    "            mid=ndList[0][1]\n",
    "            k=ndList[0][0]+1\n",
    "            dx=-1\n",
    "            for i in range(2,len(ndList)):\n",
    "                n,val=ndList[i]\n",
    "                if n==k:\n",
    "                    dx=i\n",
    "                    break\n",
    "            if dx==-1:\n",
    "                left=ndList[1:]\n",
    "                right=[]\n",
    "            else:\n",
    "                left=ndList[1:dx]\n",
    "                right=ndList[dx:]\n",
    "            midNode = TreeNode(mid)\n",
    "            midNode.left=build(left)\n",
    "            midNode.right=build(right)\n",
    "            return midNode\n",
    "        return build(ndList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        def dfs(s, sep):\n",
    "            n = len(s)\n",
    "            if n == 0: return None\n",
    "            tmp, rt = \"\", \"\"\n",
    "            i1, i2 = -1, -1\n",
    "            for i in range(n):\n",
    "                if s[i] == '-':\n",
    "                    tmp += s[i]\n",
    "                    if tmp == sep and s[i + 1] != '-':\n",
    "                        if rt == \"\":\n",
    "                            rt = s[0 : i - len(tmp) + 1]\n",
    "                        if i1 == -1:\n",
    "                            i1 = i + 1\n",
    "                        elif i2 == -1:\n",
    "                            i2 = i + 1\n",
    "                else:\n",
    "                    tmp = \"\"\n",
    "            # print(f's={s}, rt={rt}, sep={sep}')  \n",
    "            root = TreeNode(int(rt) if rt != \"\" else int(s))\n",
    "            nsep = sep + \"-\"\n",
    "            if i1 == - 1 and i2 == -1:\n",
    "                return root\n",
    "            elif i2 == -1:\n",
    "                root.left = dfs(s[i1:], nsep) \n",
    "            else:\n",
    "                root.left = dfs(s[i1: i2 - len(sep)], nsep)\n",
    "                root.right = dfs(s[i2:], nsep)\n",
    "            return root\n",
    "        return dfs(traversal, \"-\")\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        sp=traversal.split('-')\n",
    "        ndList=list()\n",
    "        k=0\n",
    "        for i in sp:\n",
    "            if i=='':\n",
    "                k+=1\n",
    "            else:\n",
    "                ndList.append((k,int(i)))\n",
    "                k=1\n",
    "        def build(ndList):\n",
    "            if len(ndList)==0: return None\n",
    "            # print(ndList)\n",
    "            mid=ndList[0][1]\n",
    "            k=ndList[0][0]+1\n",
    "            dx=-1\n",
    "            for i in range(2,len(ndList)):\n",
    "                n,val=ndList[i]\n",
    "                if n==k:\n",
    "                    dx=i\n",
    "                    break\n",
    "            if dx==-1:\n",
    "                left=ndList[1:]\n",
    "                right=[]\n",
    "            else:\n",
    "                left=ndList[1:dx]\n",
    "                right=ndList[dx:]\n",
    "            midNode = TreeNode(mid)\n",
    "            midNode.left=build(left)\n",
    "            midNode.right=build(right)\n",
    "            return midNode\n",
    "        return build(ndList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        \"\"\"\n",
    "        :param traversal:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if len(traversal) == 0:\n",
    "            return None\n",
    "        first_idx = traversal.find('-')\n",
    "        if first_idx == -1:\n",
    "            return TreeNode(int(traversal))\n",
    "        first_val = int(traversal[:first_idx])\n",
    "        root = TreeNode(first_val)\n",
    "        rest = deque([i for i in traversal[first_idx:]])\n",
    "        rank_cache = ''\n",
    "        val_cache = ''\n",
    "        st = []\n",
    "        st.append((root, 0))\n",
    "        while rest:\n",
    "            first = rest[0]\n",
    "            if first == '-':\n",
    "                if val_cache:\n",
    "                    val = int(val_cache)\n",
    "                    val_cache = ''\n",
    "                    rank = len(rank_cache)\n",
    "                    rank_cache = ''\n",
    "                    while st and st[-1][1] >= rank:\n",
    "                        st.pop()\n",
    "                    newT = TreeNode(val)\n",
    "                    if st[-1][0].left is None:\n",
    "                        st[-1][0].left = newT\n",
    "                    else:\n",
    "                        st[-1][0].right = newT\n",
    "                    st.append((newT, rank))\n",
    "                    # process..\n",
    "                else:\n",
    "                    rank_cache += '-'\n",
    "                    rest.popleft()\n",
    "                    continue\n",
    "            else:\n",
    "                val_cache += first\n",
    "                rest.popleft()\n",
    "        if val_cache:\n",
    "            val = int(val_cache)\n",
    "\n",
    "            rank = len(rank_cache)\n",
    "\n",
    "            while st and st[-1][1] >= rank:\n",
    "                st.pop()\n",
    "            newT = TreeNode(val)\n",
    "            if st[-1][0].left is None:\n",
    "                st[-1][0].left = newT\n",
    "            else:\n",
    "                st[-1][0].right = newT\n",
    "            st.append((newT, rank))\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        sp=traversal.split('-')\n",
    "        ndList=list()\n",
    "        k=0\n",
    "        for i in sp:\n",
    "            if i=='':\n",
    "                k+=1\n",
    "            else:\n",
    "                ndList.append((k,int(i)))\n",
    "                k=1\n",
    "        def build(ndList):\n",
    "            if len(ndList)==0: return None\n",
    "            # print(ndList)\n",
    "            mid=ndList[0][1]\n",
    "            k=ndList[0][0]+1\n",
    "            dx=-1\n",
    "            for i in range(2,len(ndList)):\n",
    "                n,val=ndList[i]\n",
    "                if n==k:\n",
    "                    dx=i\n",
    "                    break\n",
    "            if dx==-1:\n",
    "                left=ndList[1:]\n",
    "                right=[]\n",
    "            else:\n",
    "                left=ndList[1:dx]\n",
    "                right=ndList[dx:]\n",
    "            midNode = TreeNode(mid)\n",
    "            midNode.left=build(left)\n",
    "            midNode.right=build(right)\n",
    "            return midNode\n",
    "        return build(ndList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        def construct(s, l) -> Optional[TreeNode]:\n",
    "            if len(s) == 0:\n",
    "                return\n",
    "            judge = len(s)\n",
    "            judge_2 = len(s)\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == '-':\n",
    "                    judge = i\n",
    "                    break\n",
    "            root = TreeNode(int(s[: judge]))\n",
    "            i = judge + l\n",
    "            while i < len(s):\n",
    "                if s[i] != '-':\n",
    "                    i += 1\n",
    "                else:\n",
    "                    count = 1\n",
    "                    for j in range(i + 1, len(s)):\n",
    "                        if s[j] != '-':\n",
    "                            i = j\n",
    "                            break\n",
    "                        else:\n",
    "                            count += 1\n",
    "                    if count == l:\n",
    "                        judge_2 = i \n",
    "                        break\n",
    "            if judge_2 != len(s):\n",
    "                left = s[judge + l: judge_2 - l]\n",
    "            else:\n",
    "                left = s[judge + l:]\n",
    "            right = s[judge_2: ]\n",
    "            print(left, right)\n",
    "            root.left = construct(left, l + 1)\n",
    "            root.right = construct(right, l + 1)\n",
    "            return root\n",
    "        return construct(traversal, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        if not traversal:\n",
    "            return\n",
    "        if '-' in traversal:\n",
    "            index = traversal.find('-')\n",
    "            root = TreeNode(val=int(traversal[:index]))\n",
    "        else:\n",
    "            index = len(traversal)\n",
    "            root = TreeNode(val=int(traversal))\n",
    "        # 切分左右子树\n",
    "        split_index = index + 1\n",
    "        while split_index < len(traversal):\n",
    "            if traversal[split_index] == '-' and (traversal[split_index-1] != '-' and traversal[split_index+1] != '-'):\n",
    "                break\n",
    "            split_index += 1\n",
    "        left_str = traversal[index: split_index]\n",
    "        right_str = traversal[split_index:]\n",
    "        \n",
    "        # 去掉`-`字符\n",
    "        remove_index = []\n",
    "        for i in range(1, len(left_str)):\n",
    "            if left_str[i] != '-' and left_str[i-1] == '-':\n",
    "                remove_index.append(i-1)\n",
    "        l_s = ''\n",
    "        for i in range(1, len(left_str)):\n",
    "            if i not in remove_index:\n",
    "                l_s += left_str[i]\n",
    "        remove_index = []\n",
    "        for i in range(1, len(right_str)):\n",
    "            if right_str[i] != '-' and right_str[i-1] == '-':\n",
    "                remove_index.append(i-1)\n",
    "        r_s = ''\n",
    "        for i in range(1, len(right_str)):\n",
    "            if i not in remove_index:\n",
    "                r_s += right_str[i]\n",
    "        # 递归地构建左右子树\n",
    "        root.left = self.recoverFromPreorder(l_s)\n",
    "        root.right = self.recoverFromPreorder(r_s)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        # 将先序序列转换成数组，用负号代表深度\n",
    "        arr = [0]\n",
    "        for c in traversal:\n",
    "            if c == '-':\n",
    "                if arr[-1] > 0:\n",
    "                    arr.append(0)\n",
    "                arr[-1] -= 1\n",
    "            else:\n",
    "                if arr[-1] < 0:\n",
    "                    arr.append(0)\n",
    "                arr[-1] = arr[-1] * 10 + int(c)\n",
    "\n",
    "        def DFS(deep):\n",
    "            nonlocal pos, real_deep\n",
    "            if deep != real_deep:\n",
    "                return None\n",
    "            root = TreeNode(arr[pos])\n",
    "            pos += 1\n",
    "            children = [None, None]\n",
    "            for i in range(2):\n",
    "                try:\n",
    "                    real_deep = -arr[pos]\n",
    "                    if real_deep == deep + 1:\n",
    "                        pos += 1\n",
    "                        children[i] = DFS(deep + 1)\n",
    "                    else:\n",
    "                        break\n",
    "                except:\n",
    "                    pass\n",
    "            root.left, root.right = children[0], children[1]\n",
    "            return root\n",
    "\n",
    "        pos, real_deep = 0, 0\n",
    "        return DFS(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        \"\"\"\n",
    "        :param traversal:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if len(traversal) == 0:\n",
    "            return None\n",
    "        first_idx = traversal.find('-')\n",
    "        if first_idx == -1:\n",
    "            return TreeNode(int(traversal))\n",
    "        first_val = int(traversal[:first_idx])\n",
    "        root = TreeNode(first_val)\n",
    "        rest = deque([i for i in traversal[first_idx:]])\n",
    "        rank_cache = ''\n",
    "        val_cache = ''\n",
    "        st = []\n",
    "        st.append((root, 0))\n",
    "        while rest:\n",
    "            first = rest[0]\n",
    "            if first == '-':\n",
    "                if val_cache:\n",
    "                    val = int(val_cache)\n",
    "                    val_cache = ''\n",
    "                    rank = len(rank_cache)\n",
    "                    rank_cache = ''\n",
    "                    while st and st[-1][1] >= rank:\n",
    "                        st.pop()\n",
    "                    newT = TreeNode(val)\n",
    "                    if st[-1][0].left is None:\n",
    "                        st[-1][0].left = newT\n",
    "                    else:\n",
    "                        st[-1][0].right = newT\n",
    "                    st.append((newT, rank))\n",
    "                    # process..\n",
    "                else:\n",
    "                    rank_cache += '-'\n",
    "                    rest.popleft()\n",
    "                    continue\n",
    "            else:\n",
    "                val_cache += first\n",
    "                rest.popleft()\n",
    "        if val_cache:\n",
    "            val = int(val_cache)\n",
    "\n",
    "            rank = len(rank_cache)\n",
    "\n",
    "            while st and st[-1][1] >= rank:\n",
    "                st.pop()\n",
    "            newT = TreeNode(val)\n",
    "            if st[-1][0].left is None:\n",
    "                st[-1][0].left = newT\n",
    "            else:\n",
    "                st[-1][0].right = newT\n",
    "            st.append((newT, rank))\n",
    "\n",
    "        return root\n",
    "\n",
    "a = Solution()\n",
    "print(a.recoverFromPreorder(\"1-2--3--4-5--6--7\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ddd = 1\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        if not traversal:\n",
    "            return\n",
    "        if '-' in traversal:\n",
    "            index = traversal.find('-')\n",
    "            root = TreeNode(val=int(traversal[:index]))\n",
    "        else:\n",
    "            index = len(traversal)\n",
    "            root = TreeNode(val=int(traversal))\n",
    "        # 切分左右子树\n",
    "        split_index = index + 1\n",
    "        while split_index < len(traversal):\n",
    "            if traversal[split_index] == '-' and (traversal[split_index-1] != '-' and traversal[split_index+1] != '-'):\n",
    "                break\n",
    "            split_index += 1\n",
    "        left_str = traversal[index: split_index]\n",
    "        right_str = traversal[split_index:]\n",
    "        \n",
    "        print(split_index)\n",
    "        print(left_str, right_str)\n",
    "        # 去掉`-`字符\n",
    "        remove_index = []\n",
    "        for i in range(1, len(left_str)):\n",
    "            if left_str[i] != '-' and left_str[i-1] == '-':\n",
    "                remove_index.append(i-1)\n",
    "        l_s = ''\n",
    "        for i in range(1, len(left_str)):\n",
    "            if i not in remove_index:\n",
    "                l_s += left_str[i]\n",
    "        # print(l_s)\n",
    "        # if self.ddd == 2:\n",
    "        #     assert 1== 2\n",
    "        remove_index = []\n",
    "        for i in range(1, len(right_str)):\n",
    "            if right_str[i] != '-' and right_str[i-1] == '-':\n",
    "                remove_index.append(i-1)\n",
    "        r_s = ''\n",
    "        for i in range(1, len(right_str)):\n",
    "            if i not in remove_index:\n",
    "                r_s += right_str[i]\n",
    "        # print(r_s)\n",
    "        # assert 1 == 2\n",
    "        # 递归地构建左右子树\n",
    "        root.left = self.recoverFromPreorder(l_s)\n",
    "        root.right = self.recoverFromPreorder(r_s)\n",
    "        self.ddd += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        \"\"\"\n",
    "        :param traversal:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if len(traversal) == 0:\n",
    "            return None\n",
    "        first_idx = traversal.find('-')\n",
    "        if first_idx == -1:\n",
    "            return TreeNode(int(traversal))\n",
    "        first_val = int(traversal[:first_idx])\n",
    "        root = TreeNode(first_val)\n",
    "        rest = deque([i for i in traversal[first_idx:]])\n",
    "        rank_cache = ''\n",
    "        val_cache = ''\n",
    "        prev_root = root\n",
    "        st = []\n",
    "        st.append((root, 0))\n",
    "        while rest:\n",
    "            first = rest[0]\n",
    "            if first == '-':\n",
    "                if val_cache:\n",
    "                    val = int(val_cache)\n",
    "                    val_cache = ''\n",
    "                    rank = len(rank_cache)\n",
    "                    rank_cache = ''\n",
    "                    while st and st[-1][1] >= rank:\n",
    "                        st.pop()\n",
    "                    newT = TreeNode(val)\n",
    "                    if st[-1][0].left is None:\n",
    "                        st[-1][0].left = newT\n",
    "                    else:\n",
    "                        st[-1][0].right = newT\n",
    "                    st.append((newT, rank))\n",
    "                    # process..\n",
    "                else:\n",
    "                    rank_cache += '-'\n",
    "                    rest.popleft()\n",
    "                    continue\n",
    "            else:\n",
    "                val_cache += first\n",
    "                rest.popleft()\n",
    "        if val_cache:\n",
    "            val = int(val_cache)\n",
    "\n",
    "            rank = len(rank_cache)\n",
    "\n",
    "            while st and st[-1][1] >= rank:\n",
    "                st.pop()\n",
    "            newT = TreeNode(val)\n",
    "            if st[-1][0].left is None:\n",
    "                st[-1][0].left = newT\n",
    "            else:\n",
    "                st[-1][0].right = newT\n",
    "            st.append((newT, rank))\n",
    "\n",
    "        return root\n",
    "\n",
    "a = Solution()\n",
    "print(a.recoverFromPreorder(\"1-2--3--4-5--6--7\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:\n",
    "        def dfs(traversal, start, preDepth, stack):\n",
    "            if start>=len(traversal): return\n",
    "            depth = 0\n",
    "            while traversal[start+depth]=='-':\n",
    "                depth+=1\n",
    "            start = end = start+depth\n",
    "            while end<len(traversal) and traversal[end]!='-':\n",
    "                end+=1\n",
    "            node = TreeNode(int(traversal[start:end]))\n",
    "            index = 1\n",
    "            while index<=len(stack):\n",
    "                preDepth, preNode = stack[-index]\n",
    "                if depth==preDepth+1:\n",
    "                    if preNode.left:\n",
    "                        preNode.right = node\n",
    "                    else:\n",
    "                        preNode.left = node\n",
    "                    break\n",
    "                index+=1\n",
    "            stack.append((depth, node))\n",
    "            dfs(traversal, end, preDepth, stack)\n",
    "            \n",
    "        start, depth, stack = 0, 0, []\n",
    "        dfs(traversal, start, depth, stack)\n",
    "        return stack[0][1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
